1. Title of the Invention
The present invention generally relates to Viterbi decoding method and device thereof, more particularly, relates to path trace method in Viterbi decoding method.
This application is a counterpart of Japanese application Serial Number 09-153431 filed on Jun. 11, 1997, the subject matter of which is incorporated herein by reference.
2. Description of the Related Art
A convolution coding method is one of the error correcting codes which is used in the digital communication. A Viterbi decoding algorism is known as one of a maximum likelihood decoding method in order to decode information coded by convolution coding method.
The Viterbi decoding algorism compare the received bit line with the bit line provided by the trellis diagram, and decode received bit line according to selecting a path which has the least error. A standard value called as a metric, is compared to select the path. There are a branch metric and a path metric in the metric. The branch metric is calculated according to received bit line each states at each times, and the path metric is the cumulative total of the path metric at each time. There will always be two possible paths entering each state; one of two will be eliminated by comparing the path metrics. The process as above mentioned is known as ACS process (Added Compare-Select process). A path selecting signal is memorized in the path memory. The path selecting signal is information that which path is selected at each states.
After ACS process is done with regard to the received bit line having a predetermined decoding cycle, a state having the maximum likelihood path metric which is a path metric having a best possibility for the received bit line, is selected. This state is called as the maximum likelihood state. The received bit line can be decoded by tracing the path selecting signal memorized in the path memory as the start of the maximum likelihood state. This process in the Viterbi decoding algorism is called as a path trace method.
There are two method in the path trace method. One is called as a trace forward method which traces the memorized paths by FIFO method. The other is called a trace back method which trace the memorized paths by LIFO method. The present invention relates to the trace back method.
FIG. 1 discloses a Viterbi decoding algorism of the related art.
The necessary variable to carry out this algorism are initialized (step 101). The ACS process (step 102) and the trace back method (step 103) are done until the path memory length times (At1) initialized in step 101, respectively. In step 104, whether the trace back method is done for all of the decoding bit line should be decoded or not, is decided. If not, the ACS process is done until the path stop length times (At2) initialized in step 101, and the trace back method is done until the path memory length times (At1). Again, in step 104, whether the trace back method is done for all of the decoding bit line should be decoded or not, is decided. Steps 105 and 106 are done until the trace back method is done for all of the decoding bit line should be decoded. If the trace back method is done for all of the decoding bit line should be decoded, a frame error of the decoding bit line is decided (step 107). By the way, there is the folloing relationship between the path memory length (At1) and the path stop length (At2); At1.gtoreq.At2.
FIG. 2 discribes a sample to understand the Viterbi decoding algorism of the related art. In FIG. 2, all of the decoding bit line is 192, the path memory length (At1) is 96 and the path stop length (At2) is 32. And an address of the path memory is a cyclic address, and memorizing the path selecting signal starts from the first address of the path memory.
The ACS process is done at At1=96 times (step 101), and the trace back method is done at At1=96 times (step 102). By this process, 32 bits initialized as the path stop length (At2) is determined as the decoding bits.
Because the trace back method for all of the decoding bit line should be decoded is not done (step 104), moreover, the ACS process is done at At2=32 times (step 105), and the trace back method is doneatAtl=96 times (step 106). And 32 bits is determined as the decoding bits. The path selecting signal is memorized from the address which is the first address of the path memory.
By repeating steps 105 and 106 at three times, the trace back method with regard to all of the decoding bit line should be decoded, is finished. Thereby, the bits which is determined at the last trace back method, is 96 bits. The frame error of the decoding bit line is decided (step 107).